#!/usr/bin/python -O

## console.py
## Author:  James Thiele
## Date:    27 April 2004
## Version: 1.0

import os
import cmd
import readline



#
# Beginning of Yapay Zeka course code.
# 
import math
import random
import sys
import time

class Console(cmd.Cmd):

    def __init__(self):
        cmd.Cmd.__init__(self)
        self.prompt = "=>> "
        #self.intro  = "Welcome to console!"  ## defaults to None
	self.intro = "Merhaba. Type 'help' for help and example of usage."

    ## Command definitions ##
    def do_hist(self, args):
        """Print a list of commands that have been entered"""
        print self._hist

    def do_exit(self, args):
        """Exits from the console"""
        return -1

    ## Command definitions to support Cmd object functionality ##
    def do_EOF(self, args):
        """Exit on system end of file character"""
        return self.do_exit(args)

    def do_shell(self, args):
        """Pass command to a system shell when line begins with '!'"""
        os.system(args)

    def do_help(self, args):
        """Get help on commands
           'help' or '?' with no arguments prints a list of commands for which help is available
           'help <command>' or '? <command>' gives help on <command>
        """
        ## The only reason to define this method is for the help text in the doc string
        cmd.Cmd.do_help(self, args)
	
	print '\n'
	print 'Command are as follows:\n'
	print 'r:  ',
	cmd.Cmd.do_help(self, 'r')
	print 'l:  ',
	cmd.Cmd.do_help(self, 'l')
	print 'p:  ',
	cmd.Cmd.do_help(self, 'p')
	print 'sd:  ',
	cmd.Cmd.do_help(self, 'sd')
	print 'sb:  ',
	cmd.Cmd.do_help(self, 'sb')
	print 'psol:  ',
	cmd.Cmd.do_help(self, 'psol')
	print 'psl:  ',
	cmd.Cmd.do_help(self, 'psl')
	print 'psoll:  ',
	cmd.Cmd.do_help(self, 'psoll')
	print 'c:  ',
	cmd.Cmd.do_help(self, 'c')
	print 'ps:  ',
	cmd.Cmd.do_help(self, 'ps')

	print '\n'
	print 'An example of usage:\n'
	print 'l 3m  # load a puzzle that can be solved in 3 moves'
	print 'sb    # solve it using BSF algorithm'
	print 'c     # check if the found solution is alright'
	print 'psol  # print the solution'
	print 'psoll # print the solution showing every step being done'

    ## Override methods in Cmd object ##
    def preloop(self):
        """Initialization before prompting user for commands.
           Despite the claims in the Cmd documentaion, Cmd.preloop() is not a stub.
        """
        cmd.Cmd.preloop(self)   ## sets up command completion
        self._hist    = []      ## No history yet
        self._locals  = {}      ## Initialize execution namespace for user
        self._globals = {}

    def postloop(self):
        """Take care of any unfinished business.
           Despite the claims in the Cmd documentaion, Cmd.postloop() is not a stub.
        """
        cmd.Cmd.postloop(self)   ## Clean up command completion
        print "Exiting..."

    def precmd(self, line):
        """ This method is called after the line has been input but before
            it has been interpreted. If you want to modifdy the input line
            before execution (for example, variable substitution) do it here.
        """
        self._hist += [ line.strip() ]
        return line

    def postcmd(self, stop, line):
        """If you want to stop the console, return something that evaluates to true.
           If you want to do some post command processing, do it here.
        """
        return stop

    def emptyline(self):    
        """Do nothing on empty input line"""
        pass

    def default(self, line):       
        """Called on an input line when the command prefix is not recognized.
           In that case we execute the line as Python code.
        """
        try:
            exec(line) in self._locals, self._globals
        except Exception, e:
            print e.__class__, ":", e


    # Yapay Zeka
    def do_about(self, args):
	print 'The 8-puzzle project for Yapay Zeka'
	print 'by Kamil Krawczyk aka noth'
	print 'Interface code by James Thiele. Thanks James.'

    def do_r(self, args):
        """Generate a random puzzle."""
        self.randomTray()

    def do_p(self, args):
	"""Print the puzzle that's about to be solved."""
	#print self.tray
	if len(self.tray) == self.TRAY_SIZE:
	    self.echoTray(self.tray)

    def do_ps(self, args):
	"""Print the solved puzzle."""
	self.echoTray(self.SOLVED_TRAY)
	
    def do_psol(self, args):
	"""Print found solution."""
	print self.solution

    def do_psl(self, args):
	"""Print the solution length."""
	print len(self.solution)

    def do_psoll(self, args):
	"""Print the solution step by step."""
	end = len(self.solution)

	if end > 0:
	    zidx = 0

	    ctray = range(self.TRAY_SIZE)
	    for i in range(self.TRAY_SIZE):
		ctray[i] = self.tray[i]

	    for i in range(self.TRAY_SIZE):
		if ctray[i] == '0':
		    zidx = i
		    break

	    self.echoTray(ctray)
	    print ''

	    i = 0
	    while i < end:
	        if self.solution[i] == self.UP_SIGN:
		    tmp = ctray[zidx]
		    ctray[zidx] = ctray[zidx-self.TRAY_SIZE_SQRT]
		    ctray[zidx-self.TRAY_SIZE_SQRT] = tmp
		    zidx = zidx - self.TRAY_SIZE_SQRT
		elif self.solution[i] == self.DOWN_SIGN:
		    tmp = ctray[zidx]
		    ctray[zidx] = ctray[zidx+self.TRAY_SIZE_SQRT]
		    ctray[zidx+self.TRAY_SIZE_SQRT] = tmp
		    zidx = zidx + self.TRAY_SIZE_SQRT
		elif self.solution[i] == self.LEFT_SIGN:
		    tmp = ctray[zidx]
		    ctray[zidx] = ctray[zidx-1]
		    ctray[zidx-1] = tmp
		    zidx = zidx - 1
		elif self.solution[i] == self.RIGHT_SIGN:
		    tmp = ctray[zidx]
		    ctray[zidx] = ctray[zidx+1]
		    ctray[zidx+1] = tmp
		    zidx = zidx + 1
		    
		self.echoTray(ctray)
		print ''
		i = i+1

    def do_c(self, args):
	"""Check if the found solution is correct."""
	def isBoardCorrupted(tray):
	    if len(tray) != len(self.SOLVED_TRAY):
		return True

	    num = {}
	    i = 0
	    end = len(tray)
	    while i < end:
		if num.has_key(tray[i]):
		    num[tray[i]] = num[tray[i]] + 1
		else:
		    num[tray[i]] = 1
		i = i + 1

	    i = 0
	    while i < end:
		if not num.has_key(self.SOLVED_TRAY[i]):
		    break
		else:
		    tmp = num[self.SOLVED_TRAY[i]] - 1
		    if tmp == 0:
			num.pop(self.SOLVED_TRAY[i])
		    else:
			num[self.SOLVED_TRAY[i]] = tmp
		i = i + 1

	    if i < end:
		return True
	    else:
		return False

	# Empty solution
	if len(self.solution) <= 0:
	    i = 0
	    end = len(self.SOLVED_TRAY)
	    while i < end:
		if self.tray[i] != self.SOLVED_TRAY[i]:
		    break
		i = i + 1

	    if i == end:
		print "Solution alright."
	    #else
	    # Solution hasn't been found yet.
	    return

	if isBoardCorrupted(self.tray):
	    print "Starting tray is corrupted."
	    return

	zidx = 0
	ctray = range(self.TRAY_SIZE)
	i = 0
	while i < self.TRAY_SIZE:
	    ctray[i] = self.tray[i]
	    if ctray[i] == '0':
		zidx = i
	    i = i + 1

	i = 0
	end = len(self.solution)
	step = 1
	while i < end:
	    can = self.canGo(zidx)
	    go = self.solution[i]

	    if go == self.UP_SIGN  and  can&self.UP != 0:
		tmp = ctray[zidx]
		ctray[zidx] = ctray[zidx-self.TRAY_SIZE_SQRT]
		ctray[zidx-self.TRAY_SIZE_SQRT] = tmp
		zidx = zidx - self.TRAY_SIZE_SQRT
	    elif go == self.LEFT_SIGN  and  can&self.LEFT != 0:
		tmp = ctray[zidx]
		ctray[zidx] = ctray[zidx-1]
		ctray[zidx-1] = tmp
		zidx = zidx - 1
	    elif go == self.DOWN_SIGN  and  can&self.DOWN != 0:
		tmp = ctray[zidx]
		ctray[zidx] = ctray[zidx+self.TRAY_SIZE_SQRT]
		ctray[zidx+self.TRAY_SIZE_SQRT] = tmp
		zidx = zidx + self.TRAY_SIZE_SQRT
	    elif go == self.RIGHT_SIGN  and  can&self.RIGHT != 0:
		tmp = ctray[zidx]
		ctray[zidx] = ctray[zidx+1]
		ctray[zidx+1] = tmp
		zidx = zidx + 1
	    else:
		print "Error in solution. Step number "+str(step)+", move "+go
		return

	    step = step + 1
	    i = i + 1

	i = 0
	end = len(self.SOLVED_TRAY)
	while i < end:
	    if ctray[i] != self.SOLVED_TRAY[i]:
		break
	    i = i + 1

	if i == end:
	    print "Solution okey."
	else:
	    print "Solution doesn't lead to a solved board."


	

    def do_sd(self, args):
	"""Solve the puzzle using DSF."""
	hist = {}
	moves = {}
	pos = moves
	solved = True
	zidx = 0
	counter = 0
	start_time = time.time()

	if len(self.tray) <= 0:
	    self.randomTray()
	self.solution = []

	#ctray = self.tray
	ctray = range(self.TRAY_SIZE)
	for i in range(self.TRAY_SIZE):
	    ctray[i] = self.tray[i]

	# Find an index of the empty grid
	for i in range(self.TRAY_SIZE):
	    if ctray[i] == '0':
		zidx = i
		break

	#print 'Start:'
	#self.echoTray(ctray)
	#print ''
	
	while not self.match(ctray):
	    #self.echoTray(ctray)
	    #print self.solution
	    key = ''
	    for i in ctray:
		key += i
	    if not hist.has_key(key):
		# Save a trayprint in the history.
		#hist[key] = pos
		hist[key] = True
		next = True
		    
		#print zidx
		d = self.canGo(zidx)
		#print d
		if d&self.UP != 0:
		    #if not pos.has_key(self.UP):
		    if not pos.has_key(self.UP) and (len(self.solution)==0  or self.solution[-1]!=self.DOWN_SIGN):
			next = False
			pos[self.UP] = {}
			pos[self.UP][self.GO_BACK] = pos
			pos = pos[self.UP]
			tmp = ctray[zidx]
			ctray[zidx] = ctray[zidx-self.TRAY_SIZE_SQRT]
			ctray[zidx-self.TRAY_SIZE_SQRT] = tmp
			zidx = zidx-self.TRAY_SIZE_SQRT
			self.solution.append(self.UP_SIGN)
			#print 'up'
		if next and  d&self.LEFT != 0:
		    #if not pos.has_key(self.LEFT):
		    if not pos.has_key(self.LEFT)  and  (len(self.solution)==0  or self.solution[-1]!=self.RIGHT_SIGN):
			next = False
			pos[self.LEFT] = {}
			pos[self.LEFT][self.GO_BACK] = pos
			pos = pos[self.LEFT]
			tmp = ctray[zidx]
			ctray[zidx] = ctray[zidx-1]
			ctray[zidx-1] = tmp
			zidx = zidx-1
			self.solution.append(self.LEFT_SIGN)
			#print 'left'
		if next and  d&self.DOWN != 0:
		    #if not pos.has_key(self.DOWN):
		    if not pos.has_key(self.DOWN)  and (len(self.solution)==0  or self.solution[-1]!=self.UP_SIGN):
			next = False
			# Switch to a new node.
			pos[self.DOWN] = {}
			pos[self.DOWN][self.GO_BACK] = pos
			pos = pos[self.DOWN]
			
			# Swap grids.
			tmp = ctray[zidx]
			ctray[zidx] = ctray[zidx+self.TRAY_SIZE_SQRT]
			ctray[zidx+self.TRAY_SIZE_SQRT] = tmp

			# Update 0-element index.
			zidx = zidx+self.TRAY_SIZE_SQRT
			self.solution.append(self.DOWN_SIGN)
			#print 'down'
		if next and  d&self.RIGHT != 0:
		    #if not pos.has_key(self.RIGHT):
		    if not pos.has_key(self.RIGHT)  and  (len(self.solution)==0  or self.solution[-1]!=self.LEFT_SIGN):
			next = False
			pos[self.RIGHT] = {}
			pos[self.RIGHT][self.GO_BACK] = pos
			pos = pos[self.RIGHT]
			tmp = ctray[zidx]
			ctray[zidx] = ctray[zidx+1]
			ctray[zidx+1] = tmp
			zidx = zidx+1
			self.solution.append(self.RIGHT_SIGN)
			#print 'right'
		if next:
		    if not pos.has_key(self.GO_BACK):
			solved = False
			#print "can't go back"
			break

		    # Erase now useless move trails.
		    if pos.has_key(self.RIGHT):
			pos.pop(self.RIGHT)
		    if pos.has_key(self.DOWN):
			pos.pop(self.DOWN)
		    if pos.has_key(self.LEFT):
			pos.pop(self.LEFT)
		    if pos.has_key(self.UP):
			pos.pop(self.UP)

		    # Restore previous node handle.
		    pos = pos[self.GO_BACK]

		    ## Find previous empty grid index.
		    if pos.has_key(self.RIGHT):
			old_z = zidx-1
		    elif pos.has_key(self.DOWN):
			old_z = zidx-self.TRAY_SIZE_SQRT
		    elif pos.has_key(self.LEFT):
			old_z = zidx+1
		    elif pos.has_key(self.UP):
			old_z = zidx+self.TRAY_SIZE_SQRT
			
		    # Restore previous tray layout.
		    tmp = ctray[old_z]
		    ctray[old_z] = ctray[zidx]
		    ctray[zidx] = tmp
		    zidx = old_z
		    
		    # Delete the stamp in history.
		    key = ''
		    for i in ctray:
			key += i
		    hist.pop(key)

		    self.solution.pop()
		    #print 'node up'
		    
	    else:
		# Go up.
		#for i in range(self.TRAY_SIZE):
		    #ctray[i] = key[i]
		    #if ctray[i] == '0':
			#zidx = i

		#pos = hist[key]
		#hist.pop(key)
		#pos = hist.pop(key)

		pos = pos[self.GO_BACK]

		if pos.has_key(self.RIGHT):
		    old_z = zidx-1
		elif pos.has_key(self.DOWN):
		    old_z = zidx-self.TRAY_SIZE_SQRT
		elif pos.has_key(self.LEFT):
		    old_z = zidx+1
		elif pos.has_key(self.UP):
		    old_z = zidx+self.TRAY_SIZE_SQRT

		tmp = ctray[old_z]
		ctray[old_z] = ctray[zidx]
		ctray[zidx] = tmp
		zidx = old_z

		
		key = ''
		for i in ctray:
		    key += i
		hist.pop(key)

		self.solution.pop()
		
		#print 'history up'

		
	    counter = counter + 1
	    if counter > self.MOVES_LIMIT:
		solved = False
		break
	    elif counter%1000 == 0:
		print str(counter)+" steps"

	end_time = time.time() - start_time
	if solved:
	    print "Puzzle arranged."
	else:
	    print "This puzzle is unsolvable using given rules."
	print "I've done "+str(counter)+" moves and visited "+str(len(hist))+\
	" unique states."
	print "It took "+str(end_time)+" seconds."

    def do_sb(self, args):
	"""Solve the puzzle using BSF."""
	def make_key(tray):
	    if tray[0] == '0':
		key = '9' + tray[1] + tray[2] + \
		      tray[3] + tray[4] + tray[5] + \
		      tray[6] + tray[7] + tray[8]
	    else:
		key = tray[0] + tray[1] + tray[2] + \
		      tray[3] + tray[4] + tray[5] + \
		      tray[6] + tray[7] + tray[8]

	    return int(key)
	    
	def find_solution_path(idx,level):
	    self.solution = []
	    while level > 0:
		dcode = idx%4
		if dcode == self.B_UP:
		    self.solution.insert(0,self.UP_SIGN)
		elif dcode == self.B_DOWN:
		    self.solution.insert(0,self.DOWN_SIGN)
		elif dcode == self.B_LEFT:
		    self.solution.insert(0,self.LEFT_SIGN)
		else: # right
		    self.solution.insert(0,self.RIGHT_SIGN)
		idx = idx/4
		level = level-1


	start_time = time.time()
	steps = 0
	sol_found = False

	i = 0
	end = len(self.tray)
	if end == 0:
	    self.randomTray()
	    end = len(self.tray)
	while i < end:
	    if self.tray[i] != self.SOLVED_TRAY[i]:
		break
	    i = i + 1
	if i != end:
	    #
	    hash1 = {}
	    hash2 = {}
	    ptray = hash1
	    ctray = hash2
	    level = 1
	    steps = 0
	    stlimit = 350000
	    avindeces = [0]
	    iav = 0
	    pidx = 0
	    board = range(self.TRAY_SIZE)
	    idx = ''
	    zidx = ''
	    hist = {}
	    nzidx = ''
	    key_of_solved_puzzle = make_key(self.SOLVED_TRAY)

	    #
	    ptray[0] = [range(self.TRAY_SIZE),0]
	    i = 0
	    while i < self.TRAY_SIZE:
		ptray[0][0][i] = self.tray[i]
		board[i] = self.tray[i]
		if self.tray[i] == '0':
		    zidx = i
		i = i + 1
	    ptray[0][1] = zidx

	    dcts = self.canGo(zidx)
	    if dcts&self.UP != 0:
		idx = 0
	    elif dcts&self.LEFT != 0:
		idx = 1
	    else: # down
		idx = 2
	    # Always there exist at least 2 available ways.

	    hist[make_key(board)] = None


	    while steps < stlimit:
		finish = False
		#print idx
		if steps%1000 == 0:
		    print str(steps)+" steps"

		new_state = range(self.TRAY_SIZE)
		i = 0
		while i < self.TRAY_SIZE:
		    new_state[i] = board[i]
		    i = i + 1
		d = idx%4
		if d == 0: # up
		    swap = new_state[zidx]
		    new_state[zidx] = new_state[zidx-self.TRAY_SIZE_SQRT]
		    new_state[zidx-self.TRAY_SIZE_SQRT] = swap
		    nzidx = zidx-self.TRAY_SIZE_SQRT
		elif d == 2: # down
		    swap = new_state[zidx]
		    new_state[zidx] = new_state[zidx+self.TRAY_SIZE_SQRT]
		    new_state[zidx+self.TRAY_SIZE_SQRT] = swap
		    nzidx = zidx+self.TRAY_SIZE_SQRT
		elif d == 1: # left
		    swap = new_state[zidx]
		    new_state[zidx] = new_state[zidx-1]
		    new_state[zidx-1] = swap
		    nzidx =  zidx-1
		elif d == 3: # right
		    swap = new_state[zidx]
		    new_state[zidx] = new_state[zidx+1]
		    new_state[zidx+1] = swap
		    nzidx = zidx+1

		key = make_key(new_state)
		if key == key_of_solved_puzzle:
		    # We got a solution :-)
		    sol_found = True
		    find_solution_path(idx,level)
		    steps = steps + 1
		    break
		if not hist.has_key(key):
		    hist[key] = None
		    ctray[idx] = [new_state, nzidx]
		

		# Find index of the next point that possibly will be a solution.
		old_basket = True
		while True:
		    if idx%4 != 3:
			if old_basket:
			    idx = idx + 1
			else:
			    old_basket = True
			if level != 1:
			    pmove = pidx%4
			    move = idx%4
			    if (pmove == 0 and move == 2) or \
			       (pmove == 2 and move == 0) or \
			       (pmove == 1 and move == 3) or \
			       (pmove == 3 and move == 1):
			       continue

			dcts = self.canGo(zidx)
			move = idx%4
			if ((dcts&self.UP == 0 or move != 0) and \
			   (dcts&self.DOWN == 0 or move != 2) and \
			   (dcts&self.LEFT == 0 or move != 1) and \
			   (dcts&self.RIGHT == 0 or move != 3)):
			    continue
			else:
			    break
			    
		    iav = iav + 1
		    if iav >= len(avindeces):
			if len(ctray) <= 0:
			    # Cannot do any more moves.
			    finish = True
			    break

			level = level + 1
			if level%2 == 1:
			    ptray = hash1
			    ctray = hash2
			else:
			    ptray = hash2
			    ctray = hash1

			avindeces = ptray.keys()
			iav = 0
			ctray.clear()
		    pidx = avindeces[iav]
		    old_basket = False
		    idx = 4*pidx

		    tmp = ptray[pidx]
		    i = 0
		    end = len(tmp[0])
		    while i < end:
			board[i] = tmp[0][i]
			zidx = tmp[1]
			i = i + 1

		steps = steps + 1
		if finish:
		    break
	else:
	    # 0 steps done, solved board given.
	    self.solution = ''
	    sol_found = True

	
	end_time = time.time()
	if sol_found:
	    print "Solution found."
	    print str(steps)+" steps."
	    print "Time taken to found the solution: "+str(end_time - start_time)
	else:
	    print "Board unsolvable."
	    print "On my way I've seen level "+str(level)
	    print "I have done "+str(steps)+" steps and have seen "+str(len(hist))+" different board states."
	    print "I took "+str(end_time-start_time)+" seconds."

    def do_l(self, args):
	"""Load a tray from a given file.\n\te.g. l simple.puzz"""
	args = args.split()
	if len(args) > 0:
	    try:
		i = 0
		f = open(args[0])
		line = f.readline()
		if len(self.tray) <= 0:
		    self.tray = range(self.TRAY_SIZE)
		grids = line.split()
		while len(grids) > 0  and  i < self.TRAY_SIZE:
		    for j in grids:
			self.tray[i] = j
			i = i+1
			if i >= self.TRAY_SIZE:
			    break
		    line = f.readline()
		    grids = line.split()
		f.close()
		if i < self.TRAY_SIZE:
		    print 'File "'+args[0]+'" does not contain enough grids.'
		    self.tray = []
		    return
	    except IOError, e:
		print 'Failed to open file "'+args[0]+'"'
		self.tray = []
		return
	    self.solution = []

	    # Check tray integrity.
	    d = {}
	    for i in self.tray:
		d[i] = True
	    for i in self.SOLVED_TRAY:
		if not d.has_key(i):
		    print 'Inconsistent tray data in file "'+args[0]+'".'
		    break

    def echoTray(self, tray):
	disp = ''
	for i in range(self.TRAY_SIZE_SQRT):
	    for j in range(self.TRAY_SIZE_SQRT):
		disp += tray[i*self.TRAY_SIZE_SQRT+j]+'  '
	    print disp
	    disp = ''

    

    def canGo(self, cidx):
	ret = 0

	# right
	if cidx%3 != 2:
	    ret += self.RIGHT
	# left
	if cidx%3 != 0:
	    ret += self.LEFT
	# up
	if cidx >= 3:
	    ret += self.UP
	# down
	if cidx <= 5:
	    ret += self.DOWN

	return ret

    def randomTray(self):
	indeces = range(self.TRAY_SIZE)
	
	if len(self.tray) <= 0:
	    self.tray = range(self.TRAY_SIZE)

	for i in range(self.TRAY_SIZE):
	    index = random.randint(0, self.TRAY_SIZE-1-i)
	    self.tray[indeces[index]] = str(i)
	    indeces.pop(index)
	self.solution = []

    def match(self, tray):
	solved = True
	for i in range(self.TRAY_SIZE):
	    if tray[i] != self.SOLVED_TRAY[i]:
		solved = False
		break
	return solved
	    


    TRAY_SIZE = 9
    TRAY_SIZE_SQRT = int(math.sqrt(TRAY_SIZE))
    SOLVED_TRAY = ('1','2','3','8','0','4','7','6','5')
    MOVES_LIMIT = 2000000
	
    GO_BACK = 0
    UP = 1	#	1
    LEFT = 2	#   2	    8
    DOWN = 4	#	4
    RIGHT = 8

    B_UP = 0
    B_LEFT = 1
    B_DOWN = 2
    B_RIGHT = 3

    UP_SIGN = 'u'
    DOWN_SIGN = 'd'
    LEFT_SIGN = 'l'
    RIGHT_SIGN = 'r'

    tray = []
    solution = []

# Yapay Zeka extensions end here.
# Copyleft by Kamil Krawczyk
#	      noth@irc.pl
# Feel free to send me any comments.


if __name__ == '__main__':
        console = Console()
        console . cmdloop() 
